//
// Created by francklinson on 2021/7/9.
//
#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * hash计数
     * @param nums
     * @return
     */
    int majorityElement(vector<int> &nums) {
        unordered_map<int, int> um;
        for (auto &x:nums) {
            ++um[x];
        }
        for (auto &x:um) {
            if (x.second > nums.size() / 2)
                return x.first;
        }
        return -1;
    }
};

class Solution2 { // 摩尔投票法
public:
    int majorityElement(vector<int> &nums) {
        int candidate = -1;
        int count = 0;
        /// 由于主要元素的数量过半，那么最后应该的candidate是可选的结果
        for (int &num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        /// 判断candidate是否真的过半
        count = 0;
        int length = (int)nums.size();
        for (int &num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        return count * 2 > length ? candidate : -1;
    }
};


int main() {
    vector<int> nums{1, 2, 5, 9, 5, 9, 5, 5, 5};
    Solution sol;
    cout << sol.majorityElement(nums) << endl;
    return 0;
}